package com.gitee.swsk33.algorithms.tree.huffmantree;

import lombok.Getter;

import java.util.List;

/**
 * 赫夫曼树
 */
@Getter
public class HuffmanTree<T> {

	/**
	 * 赫夫曼树根节点
	 */
	private TreeNodeWithWeight<T> root;

	/**
	 * 构造一个赫夫曼树
	 *
	 * @param nodes 传入结点集合
	 */
	public HuffmanTree(List<TreeNodeWithWeight<T>> nodes) {
		while (nodes.size() > 1) {
			// 权重最小结点
			TreeNodeWithWeight<T> minimum = nodes.get(0);
			// 先找出最小结点
			for (int i = 1; i < nodes.size(); i++) {
				if (nodes.get(i).getWeight() < minimum.getWeight()) {
					minimum = nodes.get(i);
				}
			}
			// 从列表中移除最小节点
			nodes.remove(minimum);
			// 再找权重倒数第二小的结点
			TreeNodeWithWeight<T> penultimate = nodes.get(0);
			for (int i = 1; i < nodes.size(); i++) {
				if (nodes.get(i).getWeight() < penultimate.getWeight()) {
					penultimate = nodes.get(i);
				}
			}
			// 移除倒二结点
			nodes.remove(penultimate);
			// 把两者作为左右孩子构成一个二叉树
			TreeNodeWithWeight<T> newTreeRoot = new TreeNodeWithWeight<>();
			newTreeRoot.setLeft(minimum);
			newTreeRoot.setRight(penultimate);
			newTreeRoot.setWeight(minimum.getWeight() + penultimate.getWeight());
			// 然后把这个新的二叉树节点加入结点集合
			nodes.add(newTreeRoot);
		}
		// 最后，集合中只有一个结点就是该赫夫曼树的根节点
		root = nodes.get(0);
	}

}